{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import tkinter as tk\n",
    "class tic_tac_toe:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = tk.Tk()\n",
    "        self.canvas= tk.Canvas(self.root, width=400, height=450,bg='white')\n",
    "        self.canvas.bind(\"<Button-1>\", self.callback)\n",
    "        self.create_tic_tac_toe()\n",
    "        self.canvas.pack()\n",
    "        self.width=120\n",
    "        self.padding=20\n",
    "        self.turn=0\n",
    "        self.board=[[-1 for j in range(3)] for i in range(3)]\n",
    "        self.result=-1\n",
    "        self.score={2:0,0:-1,1:1}\n",
    "        self.root.mainloop()\n",
    "    \n",
    "    def check_win(self,bd):\n",
    "        diag1=True\n",
    "        diag2=True\n",
    "        horizontal=True\n",
    "        vertical=True\n",
    "        winner=-1\n",
    "        tie=True\n",
    "        result=-1\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if self.board[i][j]==-1:\n",
    "                    tie=False\n",
    "        for i in range(3):\n",
    "            horizontal=True\n",
    "            vertical=True\n",
    "            for j in range(3):\n",
    "                if (self.board[i][j-1]!=self.board[i][j]) or self.board[i][j]==-1 :\n",
    "                    horizontal=False\n",
    "                if (self.board[j-1][i]!=self.board[j][i]) or self.board[j][i]==-1:\n",
    "                    vertical=False\n",
    "            if horizontal==True: \n",
    "                winner=self.board[i][0]\n",
    "                \n",
    "                break;\n",
    "            elif vertical==True:\n",
    "                winner=self.board[0][i]\n",
    "                \n",
    "                break;\n",
    "            if (self.board[i-1][i-1]!=self.board[i][i]) or self.board[i][i]==-1:\n",
    "                    diag1=False\n",
    "            if (self.board[2-i][i]!=self.board[2-i-1][(i+1)%3]) or self.board[2-i][i]==-1:\n",
    "                    diag2=False\n",
    "        if horizontal==False and vertical==False:\n",
    "            \n",
    "            if diag1==True:\n",
    "                \n",
    "                winner=self.board[0][0]\n",
    "            elif diag2==True:\n",
    "                winner=self.board[0][2]\n",
    "                \n",
    "        if winner!=-1:\n",
    "            result=winner\n",
    "        elif tie==True:\n",
    "            result=2\n",
    "        return result\n",
    "    def draw_x(self,x,y):\n",
    "        x_c0=2*self.padding+(self.width*y)\n",
    "        y_c0=2*self.padding+(self.width*x)\n",
    "        x_c1=(self.width*(y+1))\n",
    "        y_c1=(self.width*(x+1))\n",
    "        self.canvas.create_line(x_c0,y_c0,x_c1,y_c1,width=2)\n",
    "        x_c0=2*self.padding+(self.width*y)\n",
    "        y_c0=(self.width*(x+1))\n",
    "        x_c1=(self.width*(y+1))\n",
    "        y_c1=2*self.padding+(self.width*x)\n",
    "        self.canvas.create_line(x_c0,y_c0,x_c1,y_c1,width=2)\n",
    "    def draw_o(self,x,y):\n",
    "        x_c0=2*self.padding+(self.width*y)\n",
    "        y_c0=2*self.padding+(self.width*x)\n",
    "        x_c1=(self.width*(y+1))\n",
    "        y_c1=(self.width*(x+1))\n",
    "        self.canvas.create_oval(x_c0,y_c0,x_c1,y_c1,width=2)\n",
    "    def insert_x(self,x,y):\n",
    "        if self.board[x][y]==-1:\n",
    "            self.board[x][y]=0\n",
    "            self.draw_x(x,y)\n",
    "            self.turn=1\n",
    "        self.result= self.check_win(self.board)\n",
    "        if self.result==0:\n",
    "            self.canvas.create_text(200,415,text='X Wins',font=('',18))\n",
    "        elif self.result==1:\n",
    "            self.canvas.create_text(200,415,text='O Wins',font=('',18))\n",
    "        elif self.result==2:\n",
    "            self.canvas.create_text(200,415,text='Tie',font=('',18))\n",
    "        #print(self.result)\n",
    "    def insert_o(self,x,y):\n",
    "        if self.board[x][y]==-1:\n",
    "            self.board[x][y]=1\n",
    "            self.draw_o(x,y)\n",
    "            self.turn=0\n",
    "        self.result=self.check_win(self.board)\n",
    "        if self.result==0:\n",
    "            self.canvas.create_text(200,415,text='X Wins',font=('',18))\n",
    "        elif self.result==1:\n",
    "            self.canvas.create_text(200,415,text='O Wins',font=('',18))\n",
    "        elif self.result==2:\n",
    "            self.canvas.create_text(200,415,text='Tie',font=('',18))\n",
    "        #print(self.result)\n",
    "    def create_tic_tac_toe(self):\n",
    "        self.canvas.create_rectangle(20,20,380,380)\n",
    "        self.canvas.create_line(140,20,140,380)\n",
    "        self.canvas.create_line(260,20,260,380)\n",
    "        self.canvas.create_line(20,140,380,140)\n",
    "        self.canvas.create_line(20,260,380,260)\n",
    "    def callback(self,event):\n",
    "        if self.turn==0 and self.result==-1:\n",
    "            x_coord=-1\n",
    "            y_coord=-1\n",
    "            for i in range(3):\n",
    "                if (self.padding+(self.width*i))<event.x<(self.padding+(self.width*(i+1))):\n",
    "                    y_coord=i\n",
    "                if (self.padding+(self.width*i))<event.y<(self.padding+(self.width*(i+1))):\n",
    "                    x_coord=i\n",
    "            if x_coord!=-1 and y_coord!=-1:\n",
    "                self.insert_x(x_coord,y_coord)\n",
    "                \n",
    "                if self.result==-1 and self.turn==1:\n",
    "                    \n",
    "                    self.nextMove()\n",
    "               \n",
    "                \n",
    "    def nextMove(self):\n",
    "        move=(-1,-1)\n",
    "        score=-2\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if self.board[i][j]==-1:\n",
    "                    self.board[i][j]=1\n",
    "                    res=self.minimax(self.board,False)\n",
    "                    if res>score:\n",
    "                        score=res\n",
    "                        move=(i,j)\n",
    "                    self.board[i][j]=-1\n",
    "        if move!=(-1,-1):\n",
    "            self.insert_o(move[0],move[1])\n",
    "    def minimax(self,board,ismax):\n",
    "        res=self.check_win(board)\n",
    "        if res!=-1:\n",
    "            return self.score[res]\n",
    "        if ismax:\n",
    "            score=-2\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if board[i][j]==-1:\n",
    "                        board[i][j]=1\n",
    "                        res=self.minimax(board,False)\n",
    "                        if res>score:\n",
    "                            score=res\n",
    "                        board[i][j]=-1\n",
    "            return score\n",
    "        else:\n",
    "            score=2\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if board[i][j]==-1:\n",
    "                        board[i][j]=0\n",
    "                        res=self.minimax(board,True)\n",
    "                        if res<score:\n",
    "                            score=res\n",
    "                        board[i][j]=-1\n",
    "            return score\n",
    "        \n",
    "if __name__=='__main__':\n",
    "    tc=tic_tac_toe()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "success\n",
      "the path followed is:\n",
      "up up left down down right up up right down left down right \n",
      "[[6, 5, 2], [1, 7, 3], [4, 0, 8]]\n",
      "[[6, 5, 2], [1, 0, 3], [4, 7, 8]]\n",
      "[[6, 0, 2], [1, 5, 3], [4, 7, 8]]\n",
      "[[0, 6, 2], [1, 5, 3], [4, 7, 8]]\n",
      "[[1, 6, 2], [0, 5, 3], [4, 7, 8]]\n",
      "[[1, 6, 2], [4, 5, 3], [0, 7, 8]]\n",
      "[[1, 6, 2], [4, 5, 3], [7, 0, 8]]\n",
      "[[1, 6, 2], [4, 0, 3], [7, 5, 8]]\n",
      "[[1, 0, 2], [4, 6, 3], [7, 5, 8]]\n",
      "[[1, 2, 0], [4, 6, 3], [7, 5, 8]]\n",
      "[[1, 2, 3], [4, 6, 0], [7, 5, 8]]\n",
      "[[1, 2, 3], [4, 0, 6], [7, 5, 8]]\n",
      "[[1, 2, 3], [4, 5, 6], [7, 0, 8]]\n",
      "[[1, 2, 3], [4, 5, 6], [7, 8, 0]]\n"
     ]
    }
   ],
   "source": [
    "class puzzle_8:\n",
    "    def __init__(self):\n",
    "        self.board=[[6,5,2],[1,7,3],[4,0,8]]#initial board position\n",
    "        self.target=[[1,2,3],[4,5,6],[7,8,0]]#target board position\n",
    "        self.visited=set() #set containing the visited states\n",
    "        self.success=False #variable indicating if the puzzle is solved\n",
    "        self.path=[] #list containing the moves used in solving the puzzle\n",
    "        for i in range(3):#setting the position of empty space\n",
    "            for j in range(3):\n",
    "                if self.board[i][j]==0:\n",
    "                    self.row_pos=i\n",
    "                    self.col_pos=j\n",
    "    def swap(self,curr,dest):\n",
    "        t=self.board[curr[0]][curr[1]]\n",
    "        self.board[curr[0]][curr[1]]=self.board[dest[0]][dest[1]]\n",
    "        self.board[dest[0]][dest[1]]=t\n",
    "    def move_up(self):#moving the empty space up\n",
    "        if self.row_pos==0:\n",
    "            return False\n",
    "        self.swap((self.row_pos,self.col_pos),(self.row_pos-1,self.col_pos))\n",
    "        self.row_pos-=1\n",
    "        return True\n",
    "    def move_down(self):#moving the empty space down\n",
    "        if self.row_pos==2:\n",
    "            return False\n",
    "        self.swap((self.row_pos,self.col_pos),(self.row_pos+1,self.col_pos))\n",
    "        self.row_pos+=1\n",
    "        return True\n",
    "    def move_left(self):#moving the empty space left\n",
    "        if self.col_pos==0:\n",
    "            return False\n",
    "        self.swap((self.row_pos,self.col_pos),(self.row_pos,self.col_pos-1))\n",
    "        self.col_pos-=1\n",
    "        return True\n",
    "    def move_right(self):#moving the empty space right\n",
    "        if self.col_pos==2:\n",
    "            return False\n",
    "        self.swap((self.row_pos,self.col_pos),(self.row_pos,self.col_pos+1))\n",
    "        self.col_pos+=1\n",
    "        return True\n",
    "    def dfs_solve(self,depth,depthlimit):#function to solve the puzzle using dfs\n",
    "        if self.success==True: \n",
    "            return\n",
    "        elif depth==depthlimit:\n",
    "            return\n",
    "        elif self.board==self.target:\n",
    "            print('success')\n",
    "            self.success=True\n",
    "        elif str(self.board) in self.visited:\n",
    "            return\n",
    "        else:\n",
    "            self.visited.add(str(self.board))\n",
    "            if self.move_up():\n",
    "                self.dfs_solve(depth+1,depthlimit)\n",
    "                self.move_down()\n",
    "                if self.success:\n",
    "                    self.path.append('up')\n",
    "                    return\n",
    "            if self.move_left():\n",
    "                self.dfs_solve(depth+1,depthlimit)\n",
    "                self.move_right()\n",
    "                if self.success:\n",
    "                    self.path.append('left')\n",
    "                    return\n",
    "            if self.move_down():\n",
    "                self.dfs_solve(depth+1,depthlimit)\n",
    "                self.move_up()\n",
    "                if self.success:\n",
    "                    self.path.append('down')\n",
    "                    return\n",
    "            if self.move_right():\n",
    "                self.dfs_solve(depth+1,depthlimit)\n",
    "                self.move_left()\n",
    "                if self.success:\n",
    "                    self.path.append('right')\n",
    "                    return\n",
    "    def print_path(self):\n",
    "        for i in range(len(self.path)-1,-1,-1):\n",
    "            print(self.board)\n",
    "            if self.path[i]=='up':\n",
    "                self.move_up()\n",
    "            elif self.path[i]=='down':\n",
    "                self.move_down()\n",
    "            elif self.path[i]=='left':\n",
    "                self.move_left()\n",
    "            elif self.path[i]=='right':\n",
    "                self.move_right()\n",
    "        print(self.board)\n",
    "if __name__=='__main__':\n",
    "    p=puzzle_8()\n",
    "    for i in range(0,1000):\n",
    "        p.dfs_solve(0,i)\n",
    "        p.visited=set()\n",
    "        if p.success:\n",
    "            print('the path followed is:')\n",
    "            for j in range(len(p.path)-1,-1,-1):\n",
    "                print(p.path[j],end=' ')\n",
    "            print('')\n",
    "            p.print_path()\n",
    "            break;\n",
    "    if not p.success:\n",
    "        print('unable to solve')\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a solution\n",
      "[2, 4, 7, 3, 0, 6, 1, 5]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "def get_numof_conflict(status):  #function to count no of conflicts\n",
    "    num = 0\n",
    "    for i in range(len(status)):\n",
    "        for j in range(i + 1,len(status)):\n",
    "            if status[i] == status[j]:   #same column\n",
    "                num += 1\n",
    "            offset = j - i\n",
    "            if abs(status[i]-status[j]) == offset: #diagonal\n",
    "                num += 1\n",
    "    return num\n",
    "def  hill_climbing(status):  #function implementing hill climbing algorithm\n",
    "    convert = {}\n",
    "    length = len(status)\n",
    "    for col in range(length):         \n",
    "        for row in range(length):\n",
    "            if status[col] == row:\n",
    "                continue\n",
    "            status_copy = list(status)\n",
    "            status_copy[col] = row              #change position of one queen and get number of conflict\n",
    "            convert[(col,row)] = get_numof_conflict(status_copy)\n",
    "    \n",
    "    answers = [] \n",
    "    conflict_now = get_numof_conflict(status) #no of conflicts for initial case\n",
    "    \n",
    "    for key,value in convert.items():    #find min no of conflicts\n",
    "        if value < conflict_now:\n",
    "            conflict_now = value\n",
    "    for key,value in convert.items():\n",
    "        if value == conflict_now:\n",
    "            answers.append(key)         #get all board arrangements with min conflicts\n",
    "    \n",
    "    if len(answers) > 0:\n",
    "        x = random.randint(0,len(answers)-1) #choose an arrangement randomly from all arrangements\n",
    "        col = answers[x][0]                  #with minimum conflicts\n",
    "        row = answers[x][1]\n",
    "        status[col] = row\n",
    "    \n",
    "    return status\n",
    " \n",
    "def Queens():\n",
    "    status = [0,1,2,3,4,5,6,7] # initial state, all queens are on the diagonal\n",
    "    while get_numof_conflict(status) > 0:\n",
    "        status = hill_climbing(status)\n",
    "    print(\"Found a solution\")\n",
    "    print(status)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    Queens()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
